#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class CBTInserter
{
public:
    CBTInserter(TreeNode *root)
    {
        this->root = root;
        queue<TreeNode *> Q;

        Q.push(root);

        while (!Q.empty())
        {
            /* code */
            TreeNode *node = Q.front();
            Q.pop();
            if(node->left)
            {
                Q.push(node->left);
            }
            if(node->right)
            {
                Q.push(node->right);
            }
            if(!(node->left && node->right))
            {
                qu.push(node);
            }
        }
    }

    int insert(int val)
    {
        TreeNode *newnode = new TreeNode(val);
        TreeNode *node = qu.front();

        int ret = newnode->val;

        if(!node->left)
        {
            node->left = newnode;
        }
        else{
            node->right = newnode;
            qu.pop();
        }

        qu.push(newnode);
        return ret;
    }

    TreeNode *get_root()
    {
        return this->root;
    }

private:
    queue<TreeNode *> qu;
    TreeNode *root;
};
